1. Field of Invention
The present invention relates to a method for routing packets in a network and more particularly to a method for routing packets in a multipath network in a way that improves load-balancing with FIFO guarantees.
2. Description of Related Art
In an information network, packets of data must be routed from an entry point in the network to a destination point. The sequential ordering of packets belonging to the same flow generally must be preserved so that a FIFO condition is guaranteed (i.e., First In First Out). This requirement is most easily satisfied with a simple network topology, that is, a network where there are relatively few choices for routing packets from an entry point to a destination point, because it is not so critical to develop strategies for balancing the loads on network resources. On the other hand, the development of increasingly complex, multi-connected networks has led to problems associated with satisfying the FIFO condition while simultaneously balancing loads in a multipath network.
A network can be modeled as a directed graph G(V,E) consisting of a set V of nodes {ni} and a set E of directed links {eji} between those nodes (i.e., eji is the directed link from node i to node j.). For each node i, let Ei be the set of directed links that connect from node i to another node of the network. FIG. 2 presents a simple but illustrative hypercube model of a network with nodes numbered from 0 to 7. In FIG. 2, the directed links from node 0 are given byE0={(e10,e20,e40}.
Subsets of directed graph G=G (V, E) can be used to define directed graphs that model the routing of packets. Let {Gj} be a set of directed graphs, where each Gj is a subset of G (i.e., Gj⊂G) so that the nodes and directed links of Gj also belong to G. For node i and directed graph Gj, let Sji=(Ei∩Gj) be the subset of Gj corresponding to links leaving node ni. The indexing of {Gj} may be done, for example, by destination node. Then, in FIG. 2, for the directed graph G5 with directed links {e10,e40,e51,e54}, it follows that S50={e10,e40}.
In routing packets in the network defined by G and {Gj}, each packet entering the network at any given node i, can be marked with a index j, identifying a directed graph Gj. This index yields a successor set Sji according to the definition above. An element of Sji can be chosen according to some strategy, thereby specifying a particular link so that the packet can be forwarded to another node of V in the network. Using the same index j, a similar action can be performed at this node and subsequently until the routing process is terminated. The routing of a packet can be terminated, for example, if the successor set is empty at some node. A node where the successor set is empty is designated as a destination node for the directed graph Gj or for a packet that is being routed to this node. Other external conditions may be used to terminate the routing of a packet. For example, setting a maximum number of nodes that can be visited by a packet (often referred to as the maximum hop count) can be used in order to limit the routing of a packet when a directed graph presents inescapable cycles (i.e., the packet can never reach a node with an empty successor set).
Approaches to the routing of packets typically either utilize local network information or global network information at each node for the purpose of computing routing tables that are equivalent to the successor sets defined above. Methods requiring global network information use extensive knowledge of network topology at each node. Examples include the link state or topology broadcast algorithms. These algorithms become increasingly burdensome as the complexity of the network increases. Methods requiring local network information use only limited knowledge of network topology at each node.
Preferably, the routing tables collectively satisfy an acyclic property, whereby circular paths are eliminated in the routing of packets. In a network were one wishes to establish directed acyclic graphs for sets of destinations, one can use algorithms such as the distance vector algorithms developed in “Loop-free Multipath Routing Using Generalized Diffusing Computations”, W. T. Zaumen and J. J. Garcia-Luna-Aceves, Proc. IEEE INFOCOM 98, San Francisco, Calif., Mar. 29–Apr. 2, 1998. These algorithms define routing tables that satisfy an acyclic property so that routing paths are loop-free (i.e., no circular paths). Other approaches may lead to routing tables with undesirable loops so that paths may be cyclic. Nevertheless, many practically useful routing tables do contain transient loops due to the nature of the computation. Ideally these algorithms generate routing tables that are optimal in the sense that the routing tables prescribe paths with routing distances that are minimized; however that may not be possible in some applications, particularly when the network includes nodes that utilize different algorithms for generating routing tables.
But even with the availability of optimal loop-free routing tables, problems associated with unbalanced loading remain unresolved. As the complexity of a network increases, the problems become more severe because of the potential for more extreme imbalance.